package offer.binarytree;

import java.util.*;

/**
 * Description：
 * Author: zhangc
 * Date：2017/7/20 19:43
 */
public class BinaryTree<T> {

    public T value;
    public BinaryTree<T> left;
    public BinaryTree<T> right;

    private BinaryTree() {
    }

    public BinaryTree(T val) {
        this.value = val;
    }

    public static <T> BinaryTree<T> createBinaryTree(List<T> list) {
        if (list.size() <= 0)
            return null;
        int size = list.size();
        BinaryTree<T>[] nodes = new BinaryTree[ size ];
        for (int i = 0; i < size; i++) {
            nodes[ i ] = new BinaryTree<>(list.get(i));
        }
        BinaryTree<T> head = nodes[ 0 ];

        for (int i = 0; i < size >> 1; i++) {
            if (2 * i + 1 < size) {
                nodes[ i ].left = nodes[ 2 * i + 1 ];
            }
            if (2 * i + 2 < size)
                nodes[ i ].right = nodes[ 2 * i + 2 ];
        }
        return nodes[ 0 ];
    }


    public List<T> preOrder() {
        List<T> list = new ArrayList<>();
        preOrder(this, list);
        return list;
    }


    private void preOrder(BinaryTree<T> node, List<T> list) {
        if (node != null) {
            list.add(node.value);
            preOrder(node.left, list);
            preOrder(node.right, list);
        }
    }


    private static <T> void preOrder(BinaryTree<T> head) {
        if (head == null)
            return;
        List<T> list = new ArrayList<>();
        Stack<BinaryTree<T>> stack = new Stack<>();
        stack.push(head);
        BinaryTree<T> temp;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            System.out.println(temp.value + "--");
            if (temp.right != null)
                stack.push(temp.right);
            if (temp.left != null)
                stack.push(temp.left);
        }
    }

    private static <T> List<T> inOrder(BinaryTree<T> head) {
        if (head == null)
            return null;
        Stack<BinaryTree<T>> stack = new Stack<>();
        List<T> result = new ArrayList<>();
        stack.push(head);
        BinaryTree<T> temp;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            result.add(temp.value);
            if (temp.left != null)
                stack.push(temp.left);
            if (temp.right != null)
                stack.push(temp.right);
        }
        Collections.reverse(result);
        return result;
    }


    private static <T> void inOrderNo(BinaryTree<T> head) {
        Stack<BinaryTree<T>> stack = new Stack<>();
        BinaryTree<T> node = head;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                System.out.println(node.value);
                node = node.right;
            }
        }
    }


    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
        BinaryTree<Integer> binaryTree = createBinaryTree(list);
        List<Integer> list1 = inOrder(binaryTree);
        //System.out.println(list1);
        inOrderNo(binaryTree);
    }

}
